Round Overview
Discuss this match
Coders in division 1 faced a medium and hard problem more difficult than average. Only three coders solved the Div 1 1000 pointer. ACRush and Petr took the first and second places respectively, having solved all three problems. Even though arti_kz was the only other coder who solved the 1000 pointer, he ended being in fourth position due to nika’s three successful challenges. Due to the ‘hidden constraints’ and tough implementation of the 550 pointer, only 53 people were able to solve it.
In Division 2 a newcomer senator ranked 1st. He was followed by Cai0715 and then by another newcomer alexbft.
MatrixShiftings
Problem Details
Used as: Division Two - Level One:
Value | 300 |
Submission Rate | 881 / 1072 (82.18%) |
Success Rate | 740 / 881 (84.00%) |
High Score | kevindra for 299.96 points (0 mins 21 secs) |
Average Score | 221.02 (for 740 correct submissions) |
A matrix is given which we need to transform using shifts so that the upper-left element of matrix is value . Since the requirement is only related to the upper-left corner of the resulting matrix, the only thing that matters is which cell is going to become the upper-left element after all the shifts are done.
If the cost to make a particular cell the upper-left corner is known, then one can iterate over all valid cells and pick the cheapest cost. So if can compute the cost associated to cell (i, j), which is the minimum number of shifts required to make cell(i, j) the upper-left corner, we are done. Two observations make this really simple:-
The order of the shifts does not matter, i.e. if we denote up, right, left and down shifts be U, R, L and D, then URLDRULRD and UUDDRRRLL give the same resulting matrix.
A U followed by a D (or a R followed by a L), do not produce any change at all. For example, UUDDRRRLL and R give the same resulting matrix.
Using the above two observations, we can say that the ith row becomes the 0th row, by only up shifts, or only down shifts. If the number of rows in matrix is n, then the number of up shifts required is i, and the number of down shifts required is n-i. Hence, the number of shifts required to make the ith row the upper row = min(i, n-i). Similarly, the number of shifts required to make the jth column the left column is min(j, m-j), where m is the number of columns in matrix .
Hence, the cost of making cell (i, j) the upper-left corner of matrix is min(i, n-i) + min(j, m-j).
Let the number of rows and columns in matrix be n and m respectively. Then, we iterate over nm cells, and take the minimum over the cost of all valid cells. Finding the cost for any cell takes constant time. Hence, the solution is O(nm). If you are unfamiliar with the big-oh notation, have a look at this wonderful tutorial.
The following code implements the above algorithm in C++.
1
2
3
4
5
6
7
8
9
10
11
12
13
int minimumShifts(vector < string > matrix, int value) {
int n = matrix.size();
int m = matrix[0].size();
int ret = -1;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) // For all possible cells
if (matrix[i][j] - '0' == value) { // Check if this cell can be the lop-left cell
int cost = min(i, n - i) + min(j, m - j); // If yes, find the cost of making this cell the top-left cell
if (ret == -1 || ret > cost) // Update answer if it is uninitialized, or if the current cost is lower
ret = cost;
}
return ret;
}
Used as: Division Two - Level Two:
Value | 500 |
Submission Rate | 568 / 1072 (52.99%) |
Success Rate | 291 / 568 (51.23%) |
High Score | johnny22smart for 494.31 points (3 mins 3 secs) |
Average Score | 346.76 (for 291 correct submissions) |
Used as: Division One - Level One:
Value | 250 |
Submission Rate | 711 / 721 (98.61%) |
Success Rate | 578 / 711 (81.29%) |
High Score | Petr for 248.60 points (2 mins 8 secs) |
Average Score | 217.40 (for 578 correct submissions) |
For now, assume that we know how to answer the question “Can Manao feed i badgers?”. Then the answer to the question “What is the maximum number of badgers Manao can feed with totalFood units of food?”, can be answered by ‘asking’ the above question several times. The number of badgers Manao keeps is between 0 and N inclusive. Hence, if for each i we ask the question “Can Manao feed i badgers?”, then the answer = maximum over all i, for which the answer to the question is yes.
The jth badger needs ( hunger [j] + (i-1)* greed [j]) units of food if Manao keeps i badgers. Since the amount of food any badger eats depends only on the number of co-eaters there are, and not on who they are, it is always better to keep a badger who eats less than a badger who eats more.
Hence, amount of food required to feed i badgers = sum of minimum i terms of the N terms {( hunger [j] + (i-1)* greed [j]), 0 ≤ j ≤ N-1}
Manao can feed i badgers iff the above sum is less than or equal to totalFood .
To answer the question “Can Manao feed i badgers?”, we need to compute the food required by each badger and then select the minimum i of these values. Hence, we find O(N) values and then we sort them giving a complexity of O(Nlog N). Moreover, we ask this question N times, hence the complexity of the entire solution is O(NN*log N).
The following is an implementation of the described solution:-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int feedMost(vector < int > hunger, vector < int > greed, int totalFood) {
int N = hunger.size();
int ret = 0;
int cost[sz];
for (int i = 1; i <= N; i++) {
for (int j = 0; j < N; j++)
cost[j] = hunger[j] + (i - 1) * greed[j]; // The amount of food badger j will eat if their are i badgers in total
sort(cost, cost + numb); // Sort the amounts of food each badger needs
int total = 0;
for (int j = 0; j < i; j++) total += cost[j]; // Take the sum of the minimum i terms
if (total <= totalFood) ret = i; // Compare to totalFood
}
return ret;
}
Although an understanding of binary search was not required to solve this problem, it is pretty easy to get a O(Nlog Nlog N) solution based on exactly the above lines using binary search. Whenever we have a increasing (or decreasing) function and it is easy to find f(x), binary search can be used to answer the question, “what is the maximum value of x for which f(x) ≤ (≥) some given value?”. The solution can further be reduced to O(N*log N) by using nth_element instead of sort.
A lot of verbose has been used while describing the solution. Symbolically, “Can Manao feed i badgers?”, is actually “Is f(x) ≤ totalFood ?” where f(x) = minimum amount of food required to feed x badgers.
Used as: Division Two - Level Three:
Value | 1000 |
Submission Rate | 155 / 1072 (14.46%) |
Success Rate | 19 / 155 (12.26%) |
High Score | Renato_Ferreira for 700.72 points (20 mins 30 secs) |
Average Score | 550.59 (for 19 correct submissions) |
occ(A, X) = number of occurrences of letter A in String X.
String str = concatenation of the elements of suppliedWord
str(a, b) = The substring of str starting at index a and ending at index (b-1)
Quoting directly from the problem statement, “A string X is called a subanagram of Y if there exists a string Z such that X is an anagram of Z and Z is a subsequence of Y.” This simplifies to X is a subanagram of Y iff occ(c, X) ≤ occ(c, Y) for all alphabets c.
Lets see why the above simplification is true. Z is a subsequence of Y iff the alphabets of Z occur in the same order as in Y, which is the same as saying occ(c, Z) ≤ occ(c, Y) for all alphabets c and the alphabets occur in the correct order. Now since Z may be any anagram of X and anagram is basically a permutation of the same alphabets, the constraint on the order in which the alphabets occur can be removed. Hence, X is a subanagram of Y iff occ(c, X) ≤ occ(c, Y) for all alphabets c.
Let dp[i][j] = maximum number of parts into which str(0, j) can be divided so that the last part is str(i, j).
In verbose, dp[i][j] = maximum number of parts into which the first j letters of the given String can be divided, so that the substring from index i to j-1, inclusive, is the last part. We keep track of the last part uptil now because the next part must be a ‘superanagram’ of the current last part.
There is a simple recurrence for dp[i][j]. The last part of dp[i][j] is str(i, j). Hence, the second last part must be str(k, i) for some 0 ≤ k ≤ i-1, such that str(k, i) is a subanagram of str(i, j).
dp[i][j] = maximum number of parts into which str(0, j) can be divided so that the last part is str(i, j).
= maximum number of parts into which str(0, i) can be divided + 1, if str(i, j) is a superanagram of the last part of str(0, i) // Applying the contraint that the last part is a superanagram of the second last part
= maximum of {dp[k][i] + 1, if str(i, j) is a superanagram of str(k, i)} // Giving the second last part a name = str(k, i)
= maximum of {dp[k][i] + 1, if str(k, i) is a subanagram of str(i, j)}
= maximum of {dp[k][i] + 1, if occ(c, str(k, i)) ≤ occ(c, str(i, j)) for all alphabets c} // Using the simplification of subanagram stated earlier
The base case is when there is no second last part, i.e i = 0. In which case, dp[i][j] = 1.
For the answer, the last part maybe any part that ends at the last letter of str. Hence, answer = maximum of {dp[i][n]}, where n = length of str.
If we store the values cnt(a, c) = number of occurrences of c in str(0, a), then occ(c, str(i, j)) = cnt(j, c) - cnt(i, c).
A naive implementation making use of everything state above has a complexity of O(n3*k), where n = length of str and k = 26. Although a good implementation of this will suffice, it is too close to the time limit. Hence, during the competition one could create a large test data and check if the implementation runs within time limit or else one could use the observation below to get rid of the factor k in the complexity of the solution.
We derived that dp[i][j] = maximum of {dp[k][i] + 1, if occ(c, str(k, i)) ≤ occ(c, str(i, j)) for all alphabets c}
When k = i, occ(c, str(k, i)) = 0 for all c.
Since we want maximum over all 0 ≤ k ≤ i-1, we start with k = i and keep decrementing k.
The only position where a violation in occ(c, str(k, i)) ≤ occ(c, str(i, j)) can occur is when c = str[k]. (Since that is the only place at which the value of occ(c, str(k, i)) changes.
Moreover, once the violation occurs it will always be there since occ(c, str(k, i)) will only increase if we decrease k. Hence, we do not need to check for smaller values of k.
The complexity of the solution using this approach is O(n3). The following is the code:-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int dp[505][505];
int cnt[505][26];
int maximumParts(vector < string > suppliedWord) {
// Concatenate the elements of suppliedWord
string str = "";
for (int i = 0; i < suppliedWord.size(); i++) str += suppliedWord[i];
int len = str.size();
// Find the number of occurrences of all alphabets in any prefix of str
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i < len; i++) {
memcpy(cnt[i + 1], cnt[i], sizeof(cnt[i]));
cnt[i + 1][str[i] - 'A']++;
}
// Initialize the dp[][] values to -INF, since we are taking maximums
memset(dp, -55, sizeof(dp));
// Base case initialization
for (int j = 1; j <= len; j++) dp[0][j] = 1;
// Implement the recursion
for (int j = 0; j <= len; j++)
for (int i = 1; i < j; i++) {
// current stones the count of the occurrences of the alphanets in str(k, i)
int current[26];
memset(current, 0, sizeof(current));
for (int k = i - 1; k >= 0; k--) {
current[str[k] - 'A']++; // Update the count
if (current[str[k] - 'A'] <= cnt[j][str[k] - 'A'] - cnt[i][str[k] - 'A']) // Check for violation
dp[i][j] = max(dp[i][j], dp[k][i] + 1); // If no violation, update dp[i][j]
else break;
}
}
// The final answer
int ret = 1;
for (int i = 0; i < len; i++) ret = max(ret, dp[i][len]);
return ret;
}
There is also a O(k*n2log n) solution which differs from the above described algorithm only in the last step. Happy Coding! :)
Used as: Division One - Level Two:
Value | 550 |
Submission Rate | 90 / 721 (12.48%) |
Success Rate | 53 / 90 (58.89%) |
High Score | Petr for 436.25 points (15 mins 22 secs) |
Average Score | 259.16 (for 53 correct submissions) |
We need to pay special attention to the constraint “Each element of friends will contain between 1 and 36 characters, inclusive”. This constraint, in disguise means that no one will have more than 15 friends. And in particular, Manao will have at most 15 friends.
It is expected that the reader is familiar with bitmask and dynamic programming. If not, you may have a look at this bitmask tutorial and this dynamic programming tutorial.
Let M[j] be the jth friend of Manao, i.e. the jth number listed in friends[0]. Number of friends of Manao = N.
Let us define prob[i][j] = probability that Manao visits the profiles of all his friends if i is the bitmask of Manao’s friends whose profile he has not visited, and M[j] is the friend whose profile Manao is viewing right now.
Note that the kth bit of i is 1 iff M[k]'s profile has not been visited yet.
Now we will see how to compute prob[i][j] by finding a recurrence. Manao is on M[j]'s profile with i being the bitmask of the friends whose profile he has not visited yet, and some subset of friends of M[j] is being displayed. If the next profile that Manao visits is that of M[k], then Manao would choose M[k] such that out of all possible valid choices now, going to M[k]'s profile gives him the highest probability of completing the tour. Also, the state changes from prob[i][j] to prob[(i^2k)][k] since the profile of M[k] is now visited and Manao now moves to the profile of M[k].
In other words, if the next profile Manao chooses to visit is that of M[k], then the subset being displayed was such that prob[(i^2k)][k] > prob[(i^2s)][s] for all valid s. (where p is valid iff M[p] has not been visited).
Hence, prob[i][j] = summation ((probability of M[k] being the best choice)* prob[(i^2k)][k]), 0 ≤ k ≤ N-1 and M[k] is a friend of M[j].
Also, prob[0][anything] = 1.0 since i = 0 indicates that all required profiles have been visited.
And, answer = summation ((probability of M[k] being the best choice)* prob[(ALL^2k)][k]), 0 ≤ k ≤ N-1. ALL denotes that all N bits are 1.
The only thing that remains is to find “probability of M[k] being the best choice”. Let the number of friends of M[j] be J.
If J < K , then all the friends are being displayed. Hence, M[k] is the best choice iff prob[(i^2k)][k] is highest over all prob[(i^2s)][s] for valid s.
If J ≥ K , then some subset of K friends is being displayed (all K -subsets have equal probability of being displayed).
Let b = number of s such that prob[(i^2s)][s] > prob[(i^2k)][k] over all valid s.
Then, out of the K profiles being displayed, one must be of M[k] and the remaining ( K -1) must be from the (J-b) profiles.
Therefore, probability = (number of favourable possibilities)/(total number of possiblities) = choose( K -1, J-b)/choose( K , J).
It is not a good idea to compare (prob[(i^2s)][s] > prob[(i^2k)][k]) ‘after’ choosing a fixed k, since there may be cases where prob[(i^2s)][s] = prob[(i^2k)][k]. Hence, in the implementation given below, we first sort prob[(i^2s)][s] for all valid s in descending order. Then, the number ‘b’ as used above is simply the index at which s is after sorting.
There is some trivial O(M*M) pre-computing at the beginning which is computing choose(n, r) and getting the friend relations in a ‘good form’.
The number of states i, j is 2NN. To calculate each state, the most time consuming thing we do is sort at most N terms. Hence, the complexity of the solution is O(MM + N2*2N*log N), where N is the number of friends of Manao and M is the number of people in Manglisi!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
int N, numb[40], frnd[40][40], c[20][20], M[15], KK;
double prob[(1 << 15)][15];
// The probability of a particular person being displayed, and there are 'from' friends in total
// and if none of the people who are better than him are being displayed. There are 'better' number of people better than him
double choose(int from, int better) {
if (KK > from) {
if (better) return 0.0;
else return 1.0;
} else {
if (from - better < KK) return 0.0;
else return ((double) c[from - better - 1][KK - 1] / (double) c[from][KK]);
}
}
// Computes prob[i][j]
double compute(int i, int j) {
vector < pair < double, int > > cur;
for (int k = 0; k < N; k++)
if (i & (1 << k)) // If his profile has not been visited
if (j == -1 || frnd[M[j]][M[k]]) // If either we are on Manao's profile, or M[j] is a friend of M[k]
cur.push_back(make_pair(prob[(i ^ (1 << k))][k], k));
// Sort them, so that it is easy to know how many people are better than him
sort(cur.begin(), cur.end(), greater < pair < double, int > > ());
double ret = 0.0;
for (int k = 0; k < cur.size(); k++) ret += choose(((j == -1) ? N : numb[M[j]]), k) * prob[(i ^ (1 << cur[k].second))][cur[k].second];
return ret;
}
double tourProbability(vector < string > friends, int K) {
// Compute the binomial coefficients
for (int i = 0; i < 20; i++)
for (int j = 0; j < 20; j++)
if (j > i) c[i][j] = 0;
else if (j == 0 || j == i) c[i][j] = 1;
else c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
// Get the friend of relations
KK = K;
memset(numb, 0, sizeof(numb));
memset(frnd, 0, sizeof(frnd));
int n = friends.size();
int temp;
for (int i = 1; i <= n; i++) {
stringstream ss;
ss << friends[i - 1];
while (ss >> temp) {
if (i == 1) M[numb[i]] = temp;
numb[i]++;
frnd[i][temp] = 1;
}
}
N = numb[1];
// Compute the probabilities
memset(prob, 0, sizeof(prob));
for (int i = 0; i < N; i++) prob[0][i] = 1.0;
for (int i = 1; i < (1 << N); i++)
for (int j = 0; j < N; j++) prob[i][j] = compute(i, j);
return compute((1 << N) - 1, -1);
}
SpaceshipEvacuation
Problem Details
Used as: Division One - Level Three:
Value | 1000 |
Submission Rate | 11 / 721 (1.53%) |
Success Rate | 3 / 11 (27.27%) |
High Score | ACRush for 450.92 points (45 mins 14 secs) |
Average Score | 409.00 (for 3 correct submissions) |
We will assume that the given graph is connected. If it is not, then we need to return -1.
The problem statement has an entire paragraph devoted to explaining the type of graphs allowed. In short, it says that each vertex lies within at most one cycle. Therefore, every edge is either a bridge or it is a part of a cycle. To make it easier to explain the solution, and to give an intuitive feel to the properties described below, it is recommended that you imagine the graph to be hung from vertex 0 (imagine the cycles to be circles).
Lets first consider the case where the edge is a bridge. Suppose that the bridge connects vertex v to vertex w, with v being higher (or in rigourous terms, d(v) < d(w)). Then any crew member within the subgraph hung at w must go from w to v, and any crew member outside it will never traverse this edge. In the worst case, all crew members will be initially at some vertex in the subgraph hung at w. Therefore, it is necessary and sufficient to have a total of crewSize cabins at w so that crewSize members can go from w to v.
Now comes the more tricky case, i.e. when the edge is a part of a cycle. Each cycle has an ‘exit vertex’ which is the vertex closest from this cycle to vertex 0. If a crew member enters the cycle, he can enter everywhere, but he will always exit it through the exit vertex. There are two potential ways from the entering point to the exit point and any of them can be used.
Suppose there are K + 1 vertices in some cycle. Again just to make it easier to state the solution, let us place these vertices in order on a circle and number them clockwise from 0 to K, 0 being the exit vertex. Let’s study the properties of final configurations that are able to evacuate crewSize people under the supposition that we didn’t have any cabins initially. For each vertex i, 1 ≤ i ≤ K, let A[i] be the number of cabins that we will finally have in edge (i-1) - i in direction from i to i-1, and let B[i] be the number of cabins that we finally have in edge i - (i+1) in direction from i to i+1 (where vertex K+1 is the same as vertex 0).
Suppose that we have all crewSize people in vertex i and further that m crew members travel anti-clockwise and the remaining ( crewSize - m) crew members travel clockwise. Then A[1], A[2], … A[i] ≥ m and B[i], B[i+1], …, B[k] ≥ ( crewSize - m) is a necessary condition. For some distribution of crew members, let there be p crew members in vertices 1 to i, inclusive. Out of the p crew members, min(p, m) crew members can always reach vertex 0 by travelling anti-clockwise. Hence, at most (p - min(p, m)) crew members would want to travel clockwise from i. The maximum value of (p - min(p, m)) is ( crewSize -m). Hence, we have just showed that if A[1], A[2], … A[i] ≥ m then B[i] = ( crewSize -m), since more than that would never be required. By symmetry, we have B[i], B[i+1], …, B[k] ≥ ( crewSize - m) implies A[i] = m. If we eliminate the parameter m, we have proved that for any i, A[i] + B[i] = crewSize , A[1], A[2], … A[i] ≥ A[i] and B[i] ≤ B[i], B[i+1], …, B[k]. Since this is true for all i, we have the following necessary and sufficient conditions,
A[1] ≥ A[2] ≥ … ≥ A[K], B[1] ≤ B[2] ≤ … ≤ B[K] and A[i] + B[i] = crewSize for all 1 ≤ i ≤ K.
Now lets return to the case when we already have some cabins initially. We have (A_ini[1], …, A_ini[K]) and (B_ini[1], …, B_ini[K]). We need to find (A[1], …, A[K]) and (B[1], …, B[K]) such that cost = summation { max(A[i]-A_ini[i], 0) + max(B[i]-B_ini[i], 0) } is minimized. This can be done easily using dynamic programming.
DP[i]j] = minimum number of cabins that need to be added if we have considered vertices 1, 2, …, i and B[i] = j.
The recurrence is as follows:-
DP[i]j] = minimum number of cabins that need to be added if we have considered vertices 1, 2, …, i and B[i] = j
= minimum of {(minimum number of cabins that need to be added if we have considered vertices 1, 2, …, i-1 and B[i-1] = k) + max(( crewSize -j)-A_ini[i], 0) + max(j-B_ini[i], 0)} over all 0 ≤ k ≤ j
= minimum of {DP[i-1][k] + max(( crewSize -j)-A_ini[i], 0) + max(j-B_ini[i], 0)} over all 0 ≤ k ≤ j
= max(( crewSize -j)-A_ini[i], 0) + max(j-B_ini[i], 0) + minimum of {DP[i-1][k]} over all 0 ≤ k ≤ j
Note that it does not take O(j) time to compute DP[i][j], rather it takes constant time. The second term, “minimum of {DP[i-1][k]} over all 0 ≤ k ≤ j”, can be computed in constant time by having a ‘running minimum’, when we keep i constant and increment j.
It takes O(1) time to deal with bridges, and O(K* crewSize ) time to deal with cycles of length K. Hence, the complexity of the solution if O( N * crewSize ). An implementation of the above algorithm in C++ has been included below:-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
int edge[55][55];
int parent[55];
int n;
int cs;
int dp[55][100005];
int ans;
int isCycle[55][55];
void dfs(int index) {
for (int next = 0; next < n; next++)
if (edge[index][next] != -1) {
if (parent[next] == -1) {
parent[next] = index;
dfs(next);
} else if (parent[index] != next && !isCycle[index][next]) {
// then this must be a 'back edge', and hence we have found a cycle
int cur = index;
vector < int > cycle;
cycle.push_back(next);
while (cur != next) {
cycle.push_back(cur);
cur = parent[cur];
}
cycle.push_back(next);
for (int i = 0; i + 1 < cycle.size(); i++) isCycle[cycle[i]][cycle[i + 1]] = isCycle[cycle[i + 1]][cycle[i]] = true;
for (int i = 1; i + 1 < cycle.size(); i++) {
int minn = 1000000000; // The running minimum
for (int j = 0; j <= cs; j++) {
minn = min(minn, dp[i - 1][j]);
dp[i][j] = minn + max((cs - j) - edge[cycle[i]][cycle[i - 1]], 0) + max(j - edge[cycle[i]][cycle[i + 1]], 0);
}
}
int minn = 1000000000;
for (int i = 0; i <= cs; i++) minn = min(minn, dp[cycle.size() - 2][i]);
ans += minn;
}
}
}
int additionalCabins(int N, vector < string > tunnelNetwork, int crewSize) {
// Get the initial edges
n = N;
cs = crewSize;
ans = 0;
int a, b, c, d;
memset(edge, -1, sizeof(edge));
for (int i = 0; i < tunnelNetwork.size(); i++) {
stringstream ss;
ss << tunnelNetwork[i];
ss >> a >> b >> c >> d;
edge[a][b] = c;
edge[b][a] = d;
}
// Do a DP which marks the edges in a cycle, labels the parents of each vertex and calculates the cost for all cycles
memset(parent, -1, sizeof(parent));
parent[0] = -2;
memset(isCycle, 0, sizeof(isCycle));
dfs(0);
// Add the cost for the bridges
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++)
if (edge[i][j] != -1)
if (!isCycle[i][j]) {
if (parent[i] == j) ans += max(cs - edge[i][j], 0);
else ans += max(cs - edge[j][i], 0);
}
for (int i = 0; i < n; i++)
if (parent[i] == -1) return -1;
return ans;
}